package 回溯;

import java.util.LinkedList;
import java.util.List;

public class _面试题_08_09_括号 {
    public List<String> generateParenthesis(int n) {
        List<String> res = new LinkedList<>();
        int leftn = 0;
        int rightn = 0;
        backtrack(leftn, rightn, res, new StringBuilder(), n);
        return res;
    }

    private void backtrack(int leftn, int rightn, List<String> res, StringBuilder stringBuilder, int n) {
        if (leftn == n && rightn == n) {
            res.add(stringBuilder.toString());
            return;
        }
        if (leftn < n) {
            StringBuilder sb = new StringBuilder(stringBuilder);
            sb.append("(");
            backtrack(leftn + 1, rightn, res, sb, n);
        }
        if (rightn < leftn) {
            StringBuilder sb = new StringBuilder(stringBuilder);
            sb.append(")");
            backtrack(leftn, rightn + 1, res, sb, n);
        }
    }


}
